package polish;

// generic list of any type T
public class LinkedList <T>
{
	// declare head node and list counter variables.
	private Node head;
	private int listCount;
	
	//  constructor
	public LinkedList()
	{
		// initially the list is empty, so the head is null
		head = new Node(null);
		listCount = 0;
	}
	
	public void addLast(T data)
	// adds the element given as parameter
	// to the end of the list	
	{
		Node temp = new Node(data);
		Node current = head;
		// start at head, walk over all nodes till 
		// end of list
		while(current.getNext() != null)
		{
			current = current.getNext();
		}
		// reference the last node's link to the new node
		current.setNext(temp);
		listCount++;
	}
	
	public void add(T data, int index)
	// adds the element given at the position given
	// as parameter to the list
	{
		Node temp = new Node(data);
		Node current = head;
		// walk to the position given, make 
		// sure position doesn't exceed list size
		for(int i = 1; i < index && current.getNext() != null; i++)
		{
			current = current.getNext();
		}
		// make the new node's next the temp's next
		temp.setNext(current.getNext());
		// make the temp's next the new node's next
		current.setNext(temp);
		listCount++;
	}
	
	public T get(int index)
	// returns the element at given postion
	{
		// index must be positive
		if(index <= 0)
			return null;
		
		Node current = head.getNext();
		for(int i = 1; i < index; i++)
		{
		
			// if the element doesn't exist return null
			if(current.getNext() == null)
				return null;
			// otherwise walk over the list till
			// at index position
			current = current.getNext();
		}
		// return the requested element's data
		return current.getData();
	}
	
	public boolean remove(int index)
	// removes the element at the position given
	// as parameter in the list
	{
		// if list size is exceeded, return false
		if(index < 1 || index > size())
			return false;
		
		// otherwise walk over list find the element
		Node current = head;
		for(int i = 1; i < index; i++)
		{
			// if list is empty or element doesn't 
			// exist return false
			if(current.getNext() == null)
				return false;
			// otherwise find it walking
			current = current.getNext();
		}
		// once found, link the elements sorounding 
		// the specified one, effectively deleting it
		current.setNext(current.getNext().getNext());
		listCount--; 
		return true;
	}
	
	public int size()
	// if we'd like to know the size
	{
		return listCount;
	}
	
	
	public String toString()
	{
		Node current = head.getNext();
		String output = "";
		// walk over the entire list
		// output each element via toString()
		while(current != null)
		{
			output += "[" + current.getData().toString() + "]";
			current = current.getNext();
		}
		return output;
	}
	
	// the node class
	private class Node
	{
		// link to the next node in the list,
		// or to null if at the end
		Node next;
		// Data of this list element
		T data;
		

		//  constructor with data
		public Node(T data)
		{
			this.next = null;
			this.data = data;
		}
		
		// constructor with data and position
		public Node(T data, Node next)
		{
			this.next = next;
			this.data = data;
		}
		
		// getter and setter methods
		public T getData()
		{
			return this.data;
		}
		
		public void setData(T data)
		{
			this.data = data;
		}
		
		public Node getNext()
		{
			return this.next;
		}
		
		public void setNext(Node next)
		{
			this.next = next;
		}
	}
}